Вы разрабатываете программу для майнинга блоков в новом блокчейне. В данный момент вам нужно релизовать модуль для выбора транзакций, включенных в блок.

На вход данному модулю подается набор из $$$n$$$ транзакций, пронумерованных от $$$1$$$ до $$$n$$$. Транзакции исполняются в специальной виртуальной машине. Память данной машины состоит из $$$m$$$ локаций, пронумерованных от $$$1$$$ до $$$m$$$. Для каждой локации вам заранее известно множество локаций памяти, из которых данная транзакция производит чтения, и множество локаций памяти, в которые она производит запись. Для $$$i$$$-й транзакции обозначим эти множества как $$$RS_i$$$ и $$$WS_i$$$.

Из данного множества транзакций модуль должен выбрать некоторое подмножество и упорядочить его. Пусть модуль выбрал $$$k$$$ транзакций с номерами $$$p_1, p_2, \ldots, p_k$$$. Для возможности спекулятивного исполнения, в выбранной последовательности транзакций не должно быть конфликтов. Конфликтом называется пара транзакций, где та транзакция, которая идет раньше, записывает в некоторую локацию памяти, откуда потом читает другая транзакция. Более формально, транзакции $$$p_i$$$ и $$$p_j$$$ где $$$i < j$$$ конфликтуют, если существует такая локация памяти $$$l$$$, что $$$l \in WS_{p_i}$$$ и $$$l \in RS_{p_j}$$$.

По данному множеству транзакций вам нужно выбрать из него последовательность транзакций наибольшей возможной длины, не содержащей конфликтов. Вам не требуется находить оптимальное решение в данной задаче. Ваше решение получит количество баллов, пропорциональное длине найденной вами последовательности транзакций.